package greed

import "math"

func jump(nums []int) int {
	pos := 0 // 维护当前所能到达的最大下标位置
	n := len(nums)
	end, step := 0, 0
	// 从左至右遍历数组，到达边界 end 时，step++，更新边界
	for i := 0; i < n-1; i++ {
		if pos >= i {
			pos = max(pos, i+nums[i])
			if i == end {
				end = pos
				step++
			}
		}
	}
	return step
}

func jump2(nums []int) int {
	dp := make([]int, len(nums))
	for i := range dp {
		dp[i] = math.MaxInt
	}
	dp[0] = 0
	for i := 0; i < len(nums); i++ {
		for j := 1; j <= nums[i]; j++ {
			if i + j < len(nums) {
				dp[i+j] = min(dp[i + j], dp[i] + 1)
			}
		}
	}
	return dp[len(nums) - 1]
}